Parallel Ant Colony Optimization for TSP in Standard ML

This version is written for the Alice implementation of the Standard ML programming lanaguage. See Multi-Core Ant Colony Optimization for TSP in Haskell for an implementation using MLton SML.

This program generates a random array of distances between cities, then uses Ant Colony Optimization to find a short path traversing all the cities -- the Travelling Salesman Problem (TSP).

In this version of Ant Colony Optimization each ant starts in a random city. Paths are randomly chosed with probability inversely proportional to to the distance to the next city. At the end of its travel the ant updates the pheromone matrix with its path if it is the shortest one yet found. The probability of later ants taking a path is increased by the pheromone value on that path. Pheromone values evaporate (decrease) over time.

In this impementation weights between cities actually represent (maxDistance - dist), so we are trying to maximize the score.

The algorithm may be run locally or on multiple remote hosts. It utilizes Alice SML's Remote structure to execute the code on a remote host via ssh. The entire program, including its necessary current state (the randomly initialized city disance array, etc.) is automatically transferred to the remote host and run. The results are later returned. The remote request is made non-blocking with the spawn expression. This creates a new thread, and returns a concurrent future. The program will block later when the future is read. In parallel mode the program spawns 2 remote executions, then blocks waiting for them to complete.

Several tests were run with various random city graphs and pheromone boost values. 1000 iterations (ants), 22 cities, and 2 remote hosts were used. The best score from the 2 hosts is graphed below:

The 0 boost value is random search with pheromones disabled. The best boost value was between 5 and 10, indicating ant colony optimization performed better than random search.

Currently the program simply prints the best paths and scores found by each searching node. Other researchers have investigated having worker nodes periodically exchange pheronome matrixes, and other parallel optimizations.

The SML source code is available here.

References

Parallel Ant Colony Algorithms by Stefan Janson, Daniel Merkle, Martin Middendorf, in Parallel Metaheuristics: A New Class of Algorithms, edited by Enrique Alba, 2005.